Свойства биномиальных коэффициентов

$$\binom{n}{k} = \dfrac{n!}{k!(n-k)!}$$

Определим способ выбора $k$-элементного подмножества: * Зафиксируем перестановку на $[ 1..n]$ (одну из $n!$) и возьмем первые $k$ элементов. * Порядок первых $k$ элементов / последних $(n-k)$ элементов не влияют на выбор. - Значит каждое подмножество будет выбрано $k!(n-k)!$ раз - Всего подмножеств $\dfrac{n!}{k!(n-k)!}$ $\square$

$$\binom{n}{k} = \binom{n}{n-k}$$

$$\sum_{k=0}^{n} \binom{n}{k} = 2^n$$

$$2^n = (1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^k 1^{n-k} = \sum_{k=0}^{n} \binom{n}{k}$$ $\square$

$$\sum_{k \text{ чет}} \binom{n}{k} = \sum_{k \text{ нечет}} \binom{n}{k} \quad (\text{при } n > 0)$$

$$0 = (-1+1)^n = \sum_{k=0}^{n} \binom{n}{k}(-1)^k = \sum_{k \text{ чет}} \binom{n}{k} - \sum_{k \text{ нечет}} \binom{n}{k}$$ $\square$

$$\sum_{k=0}^{n} k \binom{n}{k} = n 2^{n-1}$$

$$\sum_{k=0}^{n} k \binom{n}{k} = \sum_{B \subseteq [ 1..n]} |B| = \sum_{B \subseteq [ 1..n]} |\overline{B}| = \sum_{B \subseteq [ 1..n]} \dfrac{(|B| + |\overline{B}|)}{2} = \dfrac{1}{2} \sum_{B \subseteq [ 1..n]} n = \dfrac{1}{2} n 2^n = n 2^{n-1}$$ $\square$